package com.zrf.base.knowledge.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * //给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 * //
 * // 说明：解集不能包含重复的子集。
 * //
 * // 示例:
 * //
 * // 输入: nums = [1,2,3]
 * //输出:
 * //[
 * //  [3],
 * //  [1],
 * //  [2],
 * //  [1,2,3],
 * //  [1,3],
 * //  [2,3],
 * //  [1,2],
 * //  []
 * //]
 * // Related Topics 位运算 数组 回溯算法
 * // 👍 877 👎 0
 *
 * @author zhouruifeng
 * @date 2020-11-16 07:35:46
 */
public class Subsets {
    public static void main(String[] args) {
        Solution solution = new Subsets().new Solution();
        System.out.println(solution.subsets(new int[]{1, 2, 3}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> subsets(int[] nums) {
//            return subSet1(nums);
            return subSet2(nums);
        }

        private List<List<Integer>> subSet2(int[] nums) {
            List<List<Integer>> ans = new ArrayList<>();
            List<Integer> t = new ArrayList<>();
            dfs(ans, t, nums, 0);
            return ans;
        }

        private void dfs(List<List<Integer>> ans, List<Integer> t, int[] nums, int current) {
            if (current == nums.length) {
                ans.add(new ArrayList<>(t));
                return;
            }
            t.add(nums[current]);
            dfs(ans, t, nums, current + 1);
            t.remove(t.size()-1);

            dfs(ans, t, nums, current + 1);
        }

        private List<List<Integer>> subSet1(int[] nums) {
            List<List<Integer>> ans = new ArrayList<>();
            List<Integer> t = new ArrayList<>();

            for (int i = 0; i < (1 << nums.length); i++) {
                t.clear();

                for (int j = 0; j <nums.length; j++) {
                    if ((i & (1 << j)) != 0) {
                        t.add(nums[j]);
                    }
                }

                ans.add(new ArrayList<>(t));
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}